#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>

using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

vector<vector<int> > threeSum(vector<int> &num);
vector<vector<int> > fourSum(vector<int> &num, int target);
int threeSumClosest(vector<int> &num, int target);
string addBinary(string a, string b);
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2);

int main(){
    /*
    int testcase[4] = {1,1,1,1};
    vector<int> test;
    for(int i=0; i<4; ++i){
        test.push_back(testcase[i]);
    }
    */
    /*
    vector<vector<int> > res = fourSum(test, 0);

    for(int i=0; i<res.size(); ++i){
        for(int j=0; j<res[i].size(); ++j){
            cout<<res[i][j]<<' ';
        }
        cout<<endl;
    }*/
    /*
    int sum = threeSumClosest(test, -100);
    cout<<sum<<endl;

    std::string a("123456");
    string b(a.crbegin(),a.crend());
    cout<<b<<endl;
    */

    string a("0");
    string b("0");
    cout<<addBinary(a,b)<<endl;

    addTwoNumbers(NULL, NULL);

    return 0;
}

vector<vector<int> > threeSum(vector<int> &num) {
    
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int> > vres;
    if(num.size() < 3){
        return vres;
    }
    set<vector<int> > res;
    sort(num.begin(), num.end());
    int left = 0;
    int right;
    for(left =0; left < num.size()-2; ++left){
        for(right = num.size()-1; right > left+1; --right){
            // binary search for mid
            vector<int>::iterator it = find(num.begin() + left + 1, 
                num.begin() + right,
                -num[left]-num[right]);
            if(it != num.begin() + right){
                // find
                vector<int> tmp;
                tmp.push_back(num[left]);
                tmp.push_back(*it);
                tmp.push_back(num[right]);
                res.insert(tmp);
            }
        }
    }


    for(set<vector<int> >::iterator it = res.begin();
        it != res.end();
        ++it){
            vres.push_back(*it);
    }


    return vres;
}

vector<vector<int> > fourSum(vector<int> &num, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<vector<int> > res;
    if(num.size() < 4){
        return res;
    }
    sort(num.begin(), num.end());

    set<vector<int> > sres;
    for(int i=0; i< num.size() -3; ++i){
        for(int j= num.size()-1; j>i+2; --j){
            int subTarget = target - num[i] - num[j];
            int left = i+1;
            int right = j-1;
            while(left < right){
                int cur = num[left] + num[right];
                if( cur == subTarget){
                    // success
                    vector<int> tmp;
                    tmp.push_back(num[i]);
                    tmp.push_back(num[left]);
                    tmp.push_back(num[right]);
                    tmp.push_back(num[j]);
                    sres.insert(tmp);
                    ++left;
                    --right;
                }
                else if( cur < subTarget){
                    ++left;
                }
                else{
                    --right;
                }
            }
        }
    }
    // add to res
    for(set<vector<int> >::iterator it = sres.begin();
        it != sres.end();
        ++it){
            res.push_back(*it);
    }

    return res;
}

int threeSumClosest(vector<int> &num, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(num.size() < 3){
        // this should not happen
        return 0;
    }

    sort(num.begin(), num.end());
    int sum = 9999;
    bool found = false;
    for(int i=0; i<num.size()-2; ++i){
        int left = i + 1;
        int right = num.size() - 1;
        while(left < right){
            int subTmp = num[i] + num[left] + num[right];
            int deltaSqud = (target - subTmp) * (target - subTmp);
            int existedSqud = (target - sum) * (target - sum);
            if(existedSqud > deltaSqud){
                sum = subTmp;
            }
            if(subTmp == target){
                // no need to continue search
                found = true;
                break;
            }
            else if(subTmp > target){
                --right;
            }
            else{
                ++left;
            }
        }
        if(found){
            break;
        }
    }
    return sum;
}

string addBinary(string a, string b) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int ia = a.size() - 1;
    int ib = b.size() - 1;
    int iw = 0;
    char *buffer = new char[(ia>ib?ia:ib)+5];
    int carry = 0;
    while(ia>=0 || ib>=0 || carry != 0){
        int abit = 0;
        int bbit = 0;
        if(ia>=0) abit = a[ia--] - '0';
        if(ib>=0) bbit = b[ib--] - '0';
        int sum = abit + bbit + carry;
        if(sum>1){
            carry = 1;
            sum -= 2;
        }
        else{
            carry = 0;
        }
        buffer[iw++] = sum + '0';
    }
    buffer[iw] = '\0';
    string tmp(buffer);
    delete []buffer;
    string res(tmp.crbegin(),tmp.crend());
    return res;
}






ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* header = new ListNode(0);
    ListNode* curNode = header;
    int carry = 0;
    while(p1 != NULL || p2!=NULL || carry!=0){
        int num1 = 0;
        int num2 = 0;
        if(p1 != NULL){
            num1 = p1->val;
            p1 = p1->next;
        }
        if(p2 != NULL){
            num2 = p2->val;
            p2 = p2->next;
        }
        int sum = num1 + num2 + carry;
        if(sum>9){
            carry = 1;
            sum -= 10;
        }
        else{
            carry = 0;
        }
        curNode->next = new ListNode(sum);
        curNode = curNode->next;
    }
    return header->next;
}
